/*-------------------------------------------------------------------------
 *
 * pruneheap.c
 *	  堆页面修剪和 HOT 链管理代码
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/access/heap/pruneheap.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/heapam.h"
#include "access/heapam_xlog.h"
#include "access/htup_details.h"
#include "access/transam.h"
#include "access/xlog.h"
#include "access/xloginsert.h"
#include "catalog/catalog.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
#include "utils/snapmgr.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"

/* 堆页面修剪和子例程的工作数据 */
typedef struct
{
	Relation	rel;

	/* 用于测试元组可见性的状态；为关系初始化 */
	TransactionId oldest_xmin;
	GlobalVisState *vistest;

	/*
	 * 如果已计算（按需完成，仅在
	 * OldSnapshotThresholdActive() 的情况下），由 TransactionIdLimitedForOldSnapshots() 设置的阈值。当元组基于有限视野即将被删除时，old_snap_used 被设置为 true，并调用 SetOldSnapshotThresholdTimestamp()。请参见
	 * heap_prune_satisfies_vacuum()。
	 */
	TimestampTz old_snap_ts;
	TransactionId old_snap_xmin;
	bool		old_snap_used;

	TransactionId new_prune_xid;	/* 页的新的修剪提示值 */
	TransactionId latestRemovedXid; /* 将被此修剪删除的最新 xid */
	int			nredirected;	/* 下面数组中的条目数量 */
	int			ndead;
	int			nunused;
	/* 累积待更改项目索引的数组 */
	OffsetNumber redirected[MaxHeapTuplesPerPage * 2];
	OffsetNumber nowdead[MaxHeapTuplesPerPage];
	OffsetNumber nowunused[MaxHeapTuplesPerPage];

	/*
	 * 如果项目 i 在上述某个数组中，则 marked[i] 为 true。
	 *
	 * 这需要是 MaxHeapTuplesPerPage + 1 长，因为 FirstOffsetNumber 为
	 * 1。否则每次访问都需要减去 1。
	 */
	bool		marked[MaxHeapTuplesPerPage + 1];

	/*
	 * 每个元组的可见性仅计算一次，出于正确性
	 * 和效率原因；有关详细信息，请参见 heap_page_prune() 中的注释。
	 * 这是一种 int8[] 类型，而不是 HTSV_Result[]，因此我们可以使用 -1 来
	 * 表示尚未计算可见性，例如，对于 LP_DEAD 项目。
	 *
	 * 与 ->marked 相同的索引方式。
	 */
	int8		htsv[MaxHeapTuplesPerPage + 1];
} PruneState;

/* 本地函数 */
static HTSV_Result fc_heap_prune_satisfies_vacuum(PruneState *fc_prstate,
											   HeapTuple fc_tup,
											   Buffer fc_buffer);
static int	fc_heap_prune_chain(Buffer fc_buffer,
							 OffsetNumber fc_rootoffnum,
							 PruneState *fc_prstate);
static void fc_heap_prune_record_prunable(PruneState *fc_prstate, TransactionId fc_xid);
static void fc_heap_prune_record_redirect(PruneState *fc_prstate,
									   OffsetNumber fc_offnum, OffsetNumber fc_rdoffnum);
static void fc_heap_prune_record_dead(PruneState *fc_prstate, OffsetNumber fc_offnum);
static void fc_heap_prune_record_unused(PruneState *fc_prstate, OffsetNumber fc_offnum);
static void fc_page_verify_redirects(Page fc_page);


/*
 * 可选地修剪并修复指定页面中的碎片。
 *
 * 这是一种机会性函数。它将仅在页面通过启发式看起来像一个修剪候选者时执行 housekeeping，并且我们
 * 可以在不阻塞的情况下获取缓冲区清理锁。
 *
 * 注意：这一点被调用得相当频繁。如果在修剪上没有任何用途，快速退出是很重要的。
 *
 * 调用者必须在缓冲区上加锁，并且必须 *不* 在其上加锁。
 */
void heap_page_prune_opt(Relation fc_relation, Buffer fc_buffer)
{
	Page		fc_page = BufferGetPage(fc_buffer);
	TransactionId fc_prune_xid;
	GlobalVisState *fc_vistest;
	TransactionId fc_limited_xmin = InvalidTransactionId;
	TimestampTz fc_limited_ts = 0;
	Size		fc_minfree;

	/*
	 * 我们在恢复模式下无法写入 WAL，因此没有必要尝试
	 * 清理页面。主节点很可能会很快发出清理 WAL 记录，
	 * 所以这并不算什么损失。
	 */
	if (RecoveryInProgress())
		return;

	/*
	 * XXX：保持 old_snapshot_threshold 测试看起来“有效”的魔法。它们
	 * 目前是坏的，关于该如何处理这些问题的讨论正在进行中。见
	 * https://www.postgresql.org/message-id/20200403001235.e6jfdll3gh2ygbuc%40alap3.anarazel.de
	 */
	if (old_snapshot_threshold == 0)
		SnapshotTooOldMagicForTest();

	/*
	 * 首先检查是否有任何可能需要修剪的内容，
	 * 如果没有 prune_xid（即没有更新/删除的潜在死元组），则确定适当的视野是浪费。
	 */
	fc_prune_xid = ((PageHeader) fc_page)->pd_prune_xid;
	if (!TransactionIdIsValid(fc_prune_xid))
		return;

	/*
	 * 检查 prune_xid 是否表明可能存在可以清理的死行。
	 *
	 * 在获取清理锁之前检查旧快照限制是可以的，因为最糟糕的情况是我们在清理方面不够积极（以此时和获取锁之间消耗的事务 ID 数量为准）。这使我们能够在页面被发现不可修剪的情况下节省大量开销。
	 *
	 * 即使设置了 old_snapshot_threshold，我们首先检查页面是否可以在没有它的情况下进行修剪。原因在于 TransactionIdLimitedForOldSnapshots() 并不便宜，并且不必要地依赖 old_snapshot_threshold 可以避免导致冲突。
	 */
	fc_vistest = GlobalVisTestFor(fc_relation);

	if (!GlobalVisTestIsRemovableXid(fc_vistest, fc_prune_xid))
	{
		if (!OldSnapshotThresholdActive())
			return;

		if (!TransactionIdLimitedForOldSnapshots(GlobalVisTestNonRemovableHorizon(fc_vistest),
												 fc_relation,
												 &fc_limited_xmin, &fc_limited_ts))
			return;

		if (!TransactionIdPrecedes(fc_prune_xid, fc_limited_xmin))
			return;
	}

	/*
	 * 当先前的 UPDATE 未能在页面上找到足够空间以容纳新元组版本，或自由空间低于关系的填充因子目标（但不低于 10%）时，我们会进行修剪。
	 *
	 * 在这里检查自由空间是可疑的，因为我们并没有对缓冲区保持任何锁；在最糟糕的情况下，我们可能会得到一个虚假的答案。不过，这种情况不太可能是*严重*错误，因为读取 pd_lower 或 pd_upper 可能是原子的。避免获取锁似乎比在这种情况下偶尔得到错误答案更重要，毕竟这只是一个启发式估计。
	 */
	fc_minfree = RelationGetTargetPageFreeSpace(fc_relation,
											 HEAP_DEFAULT_FILLFACTOR);
	fc_minfree = Max(fc_minfree, BLCKSZ / 10);

	if (PageIsFull(fc_page) || PageGetHeapFreeSpace(fc_page) < fc_minfree)
	{
		/* 好吧，试着获取独占缓冲区锁 */
		if (!ConditionalLockBufferForCleanup(fc_buffer))
			return;

		/*
		 * 既然我们已经获得了缓冲区锁，获取有关页面自由空间的准确信息，并重新检查是否进行修剪的启发式。 （我们不需要重新检查 PageIsPrunable，因为在我们保持固定时没有其他人可以进行修剪。）
		 */
		if (PageIsFull(fc_page) || PageGetHeapFreeSpace(fc_page) < fc_minfree)
		{
			int			fc_ndeleted,
						fc_nnewlpdead;

			fc_ndeleted = heap_page_prune(fc_relation, fc_buffer, InvalidTransactionId,
									   fc_vistest, fc_limited_xmin,
									   fc_limited_ts, &fc_nnewlpdead, NULL);

			/*
			 * 向 pgstats 报告回收的元组数。这是 ndeleted 减去新设置为 LP_DEAD 的项目数。
			 *
			 * 我们以这种方式推导死元组的数量，以避免完全忘记设置为 LP_DEAD 的项目，因为它们仍然需要通过 VACUUM 清理。我们只希望在报告中计算刚刚变为 LP_UNUSED 的堆内元组，而不是那些。
			 *
			 * VACUUM 在跟踪 ndeleted 时不必以相同的方式进行补偿，因为它会单独将相同的 LP_DEAD 项设置为 LP_UNUSED。
			 */
			if (fc_ndeleted > fc_nnewlpdead)
				pgstat_update_heap_dead_tuples(fc_relation,
											   fc_ndeleted - fc_nnewlpdead);
		}

		/* 然后释放缓冲区锁 */
		LockBuffer(fc_buffer, BUFFER_LOCK_UNLOCK);

		/*
		 * 我们通过选择此时不更新 FSM 来避免重复使用页面上由不相关的 UPDATEs/INSERTs 创建的任何自由空间。自由空间应该由对*该*页面的 UPDATEs 重用。
		 */
	}
}


/*
 * 在指定页面中修剪和修复碎片。
 *
 * 调用者必须在页面上保持固定和缓冲区清理锁。注意，我们
 * 不会代表调用者更新页面的 FSM 信息。调用者可能还需要
 * 在我们对数组进行截断后，考虑行指针数组长度的减少。
 *
 * vistest 和 oldest_xmin 用于区分元组是 DEAD 还是
 * RECENTLY_DEAD（见 heap_prune_satisfies_vacuum 和
 * HeapTupleSatisfiesVacuum）。如果 oldest_xmin 由
 * 调用者提供，则在查询 GlobalVisState 之前使用它。
 *
 * old_snap_xmin / old_snap_ts 需要由
 * TransactionIdLimitedForOldSnapshots 设置，或者分别为
 * InvalidTransactionId/0。
 *
 * 设置 *nnewlpdead 给调用者，指示在修剪操作中
 * 新设置 LP_DEAD 的项的数量。
 *
 * off_loc 是调用者在错误回调中使用所需的偏移位置。
 *
 * 返回此调用中从页面删除的元组数量。
 */
int heap_page_prune(Relation fc_relation, Buffer fc_buffer,
				TransactionId fc_oldest_xmin,
				GlobalVisState *fc_vistest,
				TransactionId fc_old_snap_xmin,
				TimestampTz fc_old_snap_ts,
				int *fc_nnewlpdead,
				OffsetNumber *fc_off_loc)
{
	int			fc_ndeleted = 0;
	Page		fc_page = BufferGetPage(fc_buffer);
	BlockNumber fc_blockno = BufferGetBlockNumber(fc_buffer);
	OffsetNumber fc_offnum,
				fc_maxoff;
	PruneState	fc_prstate;
	HeapTupleData fc_tup;

	/*
	 * 我们的策略是扫描页面并制作要更改的项的列表，
	 * 然后在关键区段内应用更改。这使得尽可能多的
	 * 逻辑保持在关键区段之外，同时确保
	 * WAL 重放将与正常情况一样工作。
	 *
	 * 首先，将新的 pd_prune_xid 值初始化为零（表示没有
	 * 可修剪的元组）。如果我们发现任何可能很快变得
	 * 可修剪的元组，我们将把最低相关 XID 保存在 new_prune_xid 中。同时
	 * 初始化我们的其余工作状态。
	 */
	fc_prstate.new_prune_xid = InvalidTransactionId;
	fc_prstate.rel = fc_relation;
	fc_prstate.oldest_xmin = fc_oldest_xmin;
	fc_prstate.vistest = fc_vistest;
	fc_prstate.old_snap_xmin = fc_old_snap_xmin;
	fc_prstate.old_snap_ts = fc_old_snap_ts;
	fc_prstate.old_snap_used = false;
	fc_prstate.latestRemovedXid = InvalidTransactionId;
	fc_prstate.nredirected = fc_prstate.ndead = fc_prstate.nunused = 0;
	memset(fc_prstate.marked, 0, sizeof(fc_prstate.marked));

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	fc_tup.t_tableOid = RelationGetRelid(fc_prstate.rel);

	/*
	 * 确定所有元组的 HTSV。
	 *
	 * 这是正确性的要求，以处理运行 HTSV
	 * 两次可能导致不同结果的情况（例如，RECENTLY_DEAD 可以变为
	 * DEAD，如果另一个检查的项导致 GlobalVisTestIsRemovableFullXid()
	 * 更新视野，INSERT_IN_PROGRESS 可以变为 DEAD，如果插入事务中止，...）。
	 * 这可能导致 heap_prune_chain() 在元组被多次访问时行为不正确，
	 * 一次是通过 heap_prune_chain() 直接访问，另一次是通过 HOT 链接。
	 *
	 * 这对性能也是有好处的。页面内的元组最常以递减的偏移储存（同时项以递增的偏移储存）。在处理页面上所有元组时，这导致在页面内以递减的偏移读取内存，具有可变的步幅。
	 * 这对于 CPU 预取器来说是很难处理的。以相反的顺序处理项（因此以递增的顺序处理元组）显著提高了预取效率/减少了缓存未命中的数量。
	 */
	for (fc_offnum = fc_maxoff;
		 fc_offnum >= FirstOffsetNumber;
		 fc_offnum = OffsetNumberPrev(fc_offnum))
	{
		ItemId		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		HeapTupleHeader fc_htup;

		/* 如果插槽不包含元组，则无需操作 */
		if (!ItemIdIsNormal(fc_itemid))
		{
			fc_prstate.htsv[fc_offnum] = -1;
			continue;
		}

		fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_itemid);
		fc_tup.t_data = fc_htup;
		fc_tup.t_len = ItemIdGetLength(fc_itemid);
		ItemPointerSet(&(fc_tup.t_self), fc_blockno, fc_offnum);

		/*
		 * 设置偏移量以便我们可以在处理此元组时显示它
		 * 以及发生的任何错误。
		 */
		if (fc_off_loc)
			*fc_off_loc = fc_offnum;

		fc_prstate.htsv[fc_offnum] = fc_heap_prune_satisfies_vacuum(&fc_prstate, &fc_tup,
														   fc_buffer);
	}

	/* 扫描页面 */
	for (fc_offnum = FirstOffsetNumber;
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_itemid;

		/* 忽略作为先前链的一部分已处理的项 */
		if (fc_prstate.marked[fc_offnum])
			continue;

		/* 见前面的循环 */
		if (fc_off_loc)
			*fc_off_loc = fc_offnum;

		/* 如果槽是空的或已经死亡，则无需操作 */
		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		if (!ItemIdIsUsed(fc_itemid) || ItemIdIsDead(fc_itemid))
			continue;

		/* 处理此项或项链 */
		fc_ndeleted += fc_heap_prune_chain(fc_buffer, fc_offnum, &fc_prstate);
	}

	/* 一旦处理完给定页面，就清除偏移量信息。 */
	if (fc_off_loc)
		*fc_off_loc = InvalidOffsetNumber;

	/* 应用更改时的任何错误都是关键 */
	START_CRIT_SECTION();

	/* 我们找到了任何可修剪的项目吗？ */
	if (fc_prstate.nredirected > 0 || fc_prstate.ndead > 0 || fc_prstate.nunused > 0)
	{
		/*
		 * 应用计划的项目更改，然后修复页面碎片，并更新页面的提示位
		 * 关于它是否有空的行指针。
		 */
		heap_page_prune_execute(fc_buffer,
								fc_prstate.redirected, fc_prstate.nredirected,
								fc_prstate.nowdead, fc_prstate.ndead,
								fc_prstate.nowunused, fc_prstate.nunused);

		/*
		 * 更新页面的 pd_prune_xid 字段为零，或任何即将可修剪的元组的
		 * 最低 XID。
		 */
		((PageHeader) fc_page)->pd_prune_xid = fc_prstate.new_prune_xid;

		/*
		 * 同时清除“页面已满”标志，因为重复修剪/ дефраг处理
		 * 直到页面发生其他事情是没有意义的。
		 */
		PageClearFull(fc_page);

		MarkBufferDirty(fc_buffer);

		/*
		 * 生成一个 WAL XLOG_HEAP2_PRUNE 记录，显示我们做了什么
		 */
		if (RelationNeedsWAL(fc_relation))
		{
			xl_heap_prune fc_xlrec;
			XLogRecPtr	fc_recptr;

			fc_xlrec.latestRemovedXid = fc_prstate.latestRemovedXid;
			fc_xlrec.nredirected = fc_prstate.nredirected;
			fc_xlrec.ndead = fc_prstate.ndead;

			XLogBeginInsert();
			XLogRegisterData((char *) &fc_xlrec, SizeOfHeapPrune);

			XLogRegisterBuffer(0, fc_buffer, REGBUF_STANDARD);

			/*
			 * OffsetNumber 数组实际上不在缓冲区中，但我们
			 * 假装它们在。当 XLogInsert 存储整个
			 * 缓冲区时，偏移数组也不需要存储。
			 */
			if (fc_prstate.nredirected > 0)
				XLogRegisterBufData(0, (char *) fc_prstate.redirected,
									fc_prstate.nredirected *
									sizeof(OffsetNumber) * 2);

			if (fc_prstate.ndead > 0)
				XLogRegisterBufData(0, (char *) fc_prstate.nowdead,
									fc_prstate.ndead * sizeof(OffsetNumber));

			if (fc_prstate.nunused > 0)
				XLogRegisterBufData(0, (char *) fc_prstate.nowunused,
									fc_prstate.nunused * sizeof(OffsetNumber));

			fc_recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_PRUNE);

			PageSetLSN(BufferGetPage(fc_buffer), fc_recptr);
		}
	}
	else
	{
		/*
		 * 如果我们没有修剪任何东西，但找到了新的 pd_prune_xid 字段
		 * 值，请更新它并标记缓冲区为脏。这被视为一个非 WAL 记录的提示。
		 *
		 * 如果“页面已满”标志被设置，也请清除它，因为在其他事情发生
		 * 之前，重复修剪/ дефраг处理是没有意义的。
		 */
		if (((PageHeader) fc_page)->pd_prune_xid != fc_prstate.new_prune_xid ||
			PageIsFull(fc_page))
		{
			((PageHeader) fc_page)->pd_prune_xid = fc_prstate.new_prune_xid;
			PageClearFull(fc_page);
			MarkBufferDirtyHint(fc_buffer, true);
		}
	}

	END_CRIT_SECTION();

	/* 记录新设置的 LP_DEAD 项目的数量以供调用者使用 */
	*fc_nnewlpdead = fc_prstate.ndead;

	return fc_ndeleted;
}


/*
 * 执行堆修剪的可见性检查。
 *
 * 这比仅仅使用 GlobalVisTestIsRemovableXid() 复杂，因为
 * old_snapshot_threshold。我们只想在实际上决定根据有限的视野
 * 移除一行时才增加触发旧快照错误的阈值。
 *
 * 由于费用，我们只想在必要时调用
 * TransactionIdLimitedForOldSnapshots()，即如果 pd_prune_xid 足够旧，
 * 我们可能没有在 heap_hot_prune_opt() 中这样做。但我们仍然希望能够
 * 移除在 prstate->vistest 中由于过于新而无法移除的行，但可以根据
 * old_snapshot_threshold 移除。因此，如果适当，我们会在这里按需调用
 * TransactionIdLimitedForOldSnapshots()。
 */
static HTSV_Result
fc_heap_prune_satisfies_vacuum(PruneState *fc_prstate, HeapTuple fc_tup, Buffer fc_buffer)
{
	HTSV_Result fc_res;
	TransactionId fc_dead_after;

	fc_res = HeapTupleSatisfiesVacuumHorizon(fc_tup, fc_buffer, &fc_dead_after);

	if (fc_res != HEAPTUPLE_RECENTLY_DEAD)
		return fc_res;

	/*
	 * 如果我们已经依赖于有限的 xmin，那么就没有必要再延迟了。
	 */
	if (fc_prstate->old_snap_used)
	{
		Assert(TransactionIdIsValid(fc_prstate->old_snap_xmin));

		if (TransactionIdPrecedes(fc_dead_after, fc_prstate->old_snap_xmin))
			fc_res = HEAPTUPLE_DEAD;
		return fc_res;
	}

	/*
	 * 对于 VACUUM，我们必须确保修剪 xmax 比 oldest_xmin 还要旧的元组 
	 * -- 这是在开始清理关系时确定的可见性截止点。 oldest_xmin 用于冻结
	 * 确定，我们无法冻结已死亡元组的 xmax。
	 */
	if (TransactionIdIsValid(fc_prstate->oldest_xmin) &&
		NormalTransactionIdPrecedes(fc_dead_after, fc_prstate->oldest_xmin))
		return HEAPTUPLE_DEAD;

	/*
	 * 确定在与提供的 GlobalVisState 比较时，元组是否被视为死元组。当访问修剪时，不提供 oldest_xmin。对于 vacuum，即使元组的 xmax 不比 oldest_xmin 旧，如果在 vacuum 关系开始时 GlobalVisState 已被更新，GlobalVisTestIsRemovableXid() 也可能会发现该行已死。
	 */
	if (GlobalVisTestIsRemovableXid(fc_prstate->vistest, fc_dead_after))
		return HEAPTUPLE_DEAD;

	/*
	 * 如果 GlobalVisTestIsRemovableXid() 不足以找到已死的行，并且启用了 old_snapshot_threshold，则尝试使用降低的前沿。
	 */
	if (OldSnapshotThresholdActive())
	{
		/* 还没有确定有限前沿，请求 */
		if (!TransactionIdIsValid(fc_prstate->old_snap_xmin))
		{
			TransactionId fc_horizon =
			GlobalVisTestNonRemovableHorizon(fc_prstate->vistest);

			TransactionIdLimitedForOldSnapshots(fc_horizon, fc_prstate->rel,
												&fc_prstate->old_snap_xmin,
												&fc_prstate->old_snap_ts);
		}

		if (TransactionIdIsValid(fc_prstate->old_snap_xmin) &&
			TransactionIdPrecedes(fc_dead_after, fc_prstate->old_snap_xmin))
		{
			/*
			 * 基于 snapshot_too_old 将要移除行。需要提高阈值，以便有问题的访问会报错。
			 */
			Assert(!fc_prstate->old_snap_used);
			SetOldSnapshotThresholdTimestamp(fc_prstate->old_snap_ts,
											 fc_prstate->old_snap_xmin);
			fc_prstate->old_snap_used = true;
			fc_res = HEAPTUPLE_DEAD;
		}
	}

	return fc_res;
}


/*
 * 修剪指定的行指针或从行指针起源的 HOT 链。
 *
 * 如果该项是一个索引引用的元组（即不是仅堆元组），
 * 则通过移除 HOT 链开始的所有 DEAD 元组来修剪 HOT 链。我们还会修剪任何在 DEAD 元组之前的 RECENTLY_DEAD 元组。
 * 这是可以的，因为在 DEAD 元组之前的 RECENTLY_DEAD 元组实际上是 DEAD 的，我们的可见性测试只不过太粗糙无法检测到。
 *
 * 通常，修剪绝不能留下仍然具有元组存储的 DEAD 元组。VACUUM 没有准备处理这种情况。这就是为什么 VACUUM 在看到一个我们最初认为正在进行的新 DEAD 元组时，第二次修剪同一堆页（而在此期间不释放其锁）。像这样重试修剪只能发生在插入事务同时中止的情况下。
 *
 * 根行指针被重定向到最新 DEAD 元组后面的元组。如果链中的所有元组都是 DEAD，根行指针标记为 LP_DEAD。（这包括简单 DEAD 元组的情况，我们将其视为长度为 1 的链。）
 *
 * 我们实际上并不在这里更改页面。我们只是向 prstate 的数组中添加显示要进行的更改的条目。要重定向的项目被添加到 redirected[] 数组中（每次重定向两个条目）；要设置为 LP_DEAD 状态的项目被添加到 nowdead[]；要设置为 LP_UNUSED 状态的项目被添加到 nowunused[]。
 *
 * 返回从页面中删除（将要删除的）元组数量。
 */
static int fc_heap_prune_chain(Buffer fc_buffer, OffsetNumber fc_rootoffnum, PruneState *fc_prstate)
{
	int			fc_ndeleted = 0;
	Page		fc_dp = (Page) BufferGetPage(fc_buffer);
	TransactionId fc_priorXmax = InvalidTransactionId;
	ItemId		fc_rootlp;
	HeapTupleHeader fc_htup;
	OffsetNumber fc_latestdead = InvalidOffsetNumber,
				fc_maxoff = PageGetMaxOffsetNumber(fc_dp),
				fc_offnum;
	OffsetNumber fc_chainitems[MaxHeapTuplesPerPage];
	int			fc_nchain = 0,
				fc_i;

	fc_rootlp = PageGetItemId(fc_dp, fc_rootoffnum);

	/*
	 * 如果是仅堆元组，则它不是 HOT 链的开始。
	 */
	if (ItemIdIsNormal(fc_rootlp))
	{
		Assert(fc_prstate->htsv[fc_rootoffnum] != -1);
		fc_htup = (HeapTupleHeader) PageGetItem(fc_dp, fc_rootlp);

		if (HeapTupleHeaderIsHeapOnly(fc_htup))
		{
			/*
			 * 如果元组是死亡状态并且不链接到其他任何东西，立即将其标记为未使用。 
			 * （如果它链接，则我们只能作为修剪其链的一部分来删除它。）
			 *
			 * 我们主要需要这个来处理中止的HOT更新，即XMIN_INVALID堆只元组。 
			 * 这些可能没有被任何链链接，因为父元组可能会在任何修剪发生之前被重新更新。 
			 * 所以我们必须能够将它们与链的修剪分开收割。 
			 * （注意，HeapTupleHeaderIsHotUpdated对于XMIN_INVALID元组永远不会返回真，因此即使在中止事务中有连续更新，这段代码也能正常工作。）
			 *
			 * 注意，我们可能首先在这里或在下面跟随一个链时到达一个死亡的堆只元组。 
			 * 无论哪个路径先到达，将标记元组为未使用。
			 */
			if (fc_prstate->htsv[fc_rootoffnum] == HEAPTUPLE_DEAD &&
				!HeapTupleHeaderIsHotUpdated(fc_htup))
			{
				fc_heap_prune_record_unused(fc_prstate, fc_rootoffnum);
				HeapTupleHeaderAdvanceLatestRemovedXid(fc_htup,
													   &fc_prstate->latestRemovedXid);
				fc_ndeleted++;
			}

			/* 没有更多的操作 */
			return fc_ndeleted;
		}
	}

	/* 从根元组开始 */
	fc_offnum = fc_rootoffnum;

	/* 当未到达链的末尾时 */
	for (;;)
	{
		ItemId		fc_lp;
		bool		fc_tupdead,
					fc_recent_dead;

		/* 正常性检查（纯粹的偏执） */
		if (fc_offnum < FirstOffsetNumber)
			break;

		/*
		 * 当数组被截断时，超过页面行指针数组末尾的偏移是可能的 
		 * （原始项必须是未使用的）
		 */
		if (fc_offnum > fc_maxoff)
			break;

		/* 如果项已经处理，停止——它绝不能是同一链 */
		if (fc_prstate->marked[fc_offnum])
			break;

		fc_lp = PageGetItemId(fc_dp, fc_offnum);

		/* 显然未使用的项不是链的一部分 */
		if (!ItemIdIsUsed(fc_lp))
			break;

		/*
		 * 如果我们正在查看重定向的根行指针，则跳到链中的第一个正常元组。 
		 * 如果我们在其他地方找到了重定向，则停止——它绝不能是同一链。
		 */
		if (ItemIdIsRedirected(fc_lp))
		{
			if (fc_nchain > 0)
				break;			/* 不在链的开始处 */
			fc_chainitems[fc_nchain++] = fc_offnum;
			fc_offnum = ItemIdGetRedirect(fc_rootlp);
			continue;
		}

		/*
		 * 同样，死亡的行指针不能是链的一部分。 
		 * （我们已经在这个函数外消除了死亡根元组的情况。）
		 */
		if (ItemIdIsDead(fc_lp))
			break;

		Assert(ItemIdIsNormal(fc_lp));
		Assert(fc_prstate->htsv[fc_offnum] != -1);
		fc_htup = (HeapTupleHeader) PageGetItem(fc_dp, fc_lp);

		/*
		 * 将元组的XMIN与先前的XMAX进行检查，如果有的话
		 */
		if (TransactionIdIsValid(fc_priorXmax) &&
			!TransactionIdEquals(HeapTupleHeaderGetXmin(fc_htup), fc_priorXmax))
			break;

		/*
		 * 好的，这个元组确实是链的一部分。
		 */
		fc_chainitems[fc_nchain++] = fc_offnum;

		/*
		 * 检查元组的可见状态。
		 */
		fc_tupdead = fc_recent_dead = false;

		switch ((HTSV_Result) fc_prstate->htsv[fc_offnum])
		{
			case HEAPTUPLE_DEAD:
				fc_tupdead = true;
				break;

			case HEAPTUPLE_RECENTLY_DEAD:
				fc_recent_dead = true;

				/*
				 * 这个元组可能很快就会变为死亡。 
				 * 更新提示字段，以便在未来重新考虑该页面的修剪。
				 */
				fc_heap_prune_record_prunable(fc_prstate,
										   HeapTupleHeaderGetUpdateXid(fc_htup));
				break;

			case HEAPTUPLE_DELETE_IN_PROGRESS:

				/*
				 * 这个元组可能很快就会变为死亡。 
				 * 更新提示字段，以便在未来重新考虑该页面的修剪。
				 */
				fc_heap_prune_record_prunable(fc_prstate,
										   HeapTupleHeaderGetUpdateXid(fc_htup));
				break;

			case HEAPTUPLE_LIVE:
			case HEAPTUPLE_INSERT_IN_PROGRESS:

				/*
				 * 如果我们想为中止进行优化，可能会考虑在看到INSERT_IN_PROGRESS时标记该页面可修剪。 
				 * 但我们不这样做。 
				 * 有关何时标记页面可修剪的相关决策，请参阅heapam.c。
				 */
				break;

			default:
				elog(ERROR, "unexpected HeapTupleSatisfiesVacuum result");
				break;
		}

		/*
		 * 记住最后一个看到的死亡元组。 
		 * 我们将越过RECENTLY_DEAD元组，以防后面还有一个死亡元组； 
		 * 但我们不能越过其他任何东西。 
		 * 我们必须确保不会错过任何死亡元组，因为在修剪后仍然具有元组存储的死亡元组将混淆VACUUM。
		 */
		if (fc_tupdead)
		{
			fc_latestdead = fc_offnum;
			HeapTupleHeaderAdvanceLatestRemovedXid(fc_htup,
												   &fc_prstate->latestRemovedXid);
		}
		else if (!fc_recent_dead)
			break;

		/*
		 * 如果元组未进行HOT更新，则我们在此
		 * HOT更新链的末尾。
		 */
		if (!HeapTupleHeaderIsHotUpdated(fc_htup))
			break;

		/* HOT意味着它不能移动到不同的分区 */
		Assert(!HeapTupleHeaderIndicatesMovedPartitions(fc_htup));

		/*
		 * 前进到下一个链成员。
		 */
		Assert(ItemPointerGetBlockNumber(&fc_htup->t_ctid) ==
			   BufferGetBlockNumber(fc_buffer));
		fc_offnum = ItemPointerGetOffsetNumber(&fc_htup->t_ctid);
		fc_priorXmax = HeapTupleHeaderGetUpdateXid(fc_htup);
	}

	/*
	 * 如果我们在链中找到了一个死亡元组，请调整HOT链，以便删除链开始处的所有死亡元组，并将根行指针适当地重定向。
	 */
	if (OffsetNumberIsValid(fc_latestdead))
	{
		/*
		 * 将每个可以从链中移除的中间项标记为未使用。
		 *
		 * 当上一个项是最后一个看到的死亡元组时，我们在重定向的正确候选项上。
		 */
		for (fc_i = 1; (fc_i < fc_nchain) && (fc_chainitems[fc_i - 1] != fc_latestdead); fc_i++)
		{
			fc_heap_prune_record_unused(fc_prstate, fc_chainitems[fc_i]);
			fc_ndeleted++;
		}

		/*
		 * 如果根条目是一个正常元组，我们正在删除它，因此计算在结果中。但更改重定向（即使是到死亡状态）不算。
		 */
		if (ItemIdIsNormal(fc_rootlp))
			fc_ndeleted++;

		/*
		 * 如果死亡元组位于链的末尾，则整个链是死亡的，根行指针可以标记为死亡。否则，只需将根重定向到正确的链成员。
		 */
		if (fc_i >= fc_nchain)
			fc_heap_prune_record_dead(fc_prstate, fc_rootoffnum);
		else
			fc_heap_prune_record_redirect(fc_prstate, fc_rootoffnum, fc_chainitems[fc_i]);
	}
	else if (fc_nchain < 2 && ItemIdIsRedirected(fc_rootlp))
	{
		/*
		 * 我们发现一个重定向项指向一个无效的后续项。这可能发生在heap_page_prune中的循环导致我们访问了一个重定向项的死亡后继，而在访问重定向项之前。我们可以通过将重定向项设置为死亡状态来清理。
		 */
		fc_heap_prune_record_dead(fc_prstate, fc_rootoffnum);
	}

	return fc_ndeleted;
}

/* 记录最低即将可修剪的XID */
static void fc_heap_prune_record_prunable(PruneState *fc_prstate, TransactionId fc_xid)
{
	/*
	 * 这应该与PageSetPrunable宏完全匹配。我们还不能直接存储到页面头中，因此我们更新工作状态。
	 */
	Assert(TransactionIdIsNormal(fc_xid));
	if (!TransactionIdIsValid(fc_prstate->new_prune_xid) ||
		TransactionIdPrecedes(fc_xid, fc_prstate->new_prune_xid))
		fc_prstate->new_prune_xid = fc_xid;
}

/* 记录要重定向的行指针 */
static void fc_heap_prune_record_redirect(PruneState *fc_prstate,
						   OffsetNumber fc_offnum, OffsetNumber fc_rdoffnum)
{
	Assert(fc_prstate->nredirected < MaxHeapTuplesPerPage);
	fc_prstate->redirected[fc_prstate->nredirected * 2] = fc_offnum;
	fc_prstate->redirected[fc_prstate->nredirected * 2 + 1] = fc_rdoffnum;
	fc_prstate->nredirected++;
	Assert(!fc_prstate->marked[fc_offnum]);
	fc_prstate->marked[fc_offnum] = true;
	Assert(!fc_prstate->marked[fc_rdoffnum]);
	fc_prstate->marked[fc_rdoffnum] = true;
}

/* 记录要标记为死亡的行指针 */
static void fc_heap_prune_record_dead(PruneState *fc_prstate, OffsetNumber fc_offnum)
{
	Assert(fc_prstate->ndead < MaxHeapTuplesPerPage);
	fc_prstate->nowdead[fc_prstate->ndead] = fc_offnum;
	fc_prstate->ndead++;
	Assert(!fc_prstate->marked[fc_offnum]);
	fc_prstate->marked[fc_offnum] = true;
}

/* 记录要标记为未使用的行指针 */
static void fc_heap_prune_record_unused(PruneState *fc_prstate, OffsetNumber fc_offnum)
{
	Assert(fc_prstate->nunused < MaxHeapTuplesPerPage);
	fc_prstate->nowunused[fc_prstate->nunused] = fc_offnum;
	fc_prstate->nunused++;
	Assert(!fc_prstate->marked[fc_offnum]);
	fc_prstate->marked[fc_offnum] = true;
}


/*
 * 执行heap_page_prune所需的实际页面更改。
 * 预计调用方在缓冲区上拥有完整的清理锁。
 */
void heap_page_prune_execute(Buffer fc_buffer,
						OffsetNumber *fc_redirected, int fc_nredirected,
						OffsetNumber *fc_nowdead, int fc_ndead,
						OffsetNumber *fc_nowunused, int fc_nunused)
{
	Page		fc_page = (Page) BufferGetPage(fc_buffer);
	OffsetNumber *fc_offnum;
	HeapTupleHeader fc_htup PG_USED_FOR_ASSERTS_ONLY;

	/* 除非有事情要做，否则不应调用 */
	Assert(fc_nredirected > 0 || fc_ndead > 0 || fc_nunused > 0);

	/* 更新所有重定向的行指针 */
	fc_offnum = fc_redirected;
	for (int fc_i = 0; fc_i < fc_nredirected; fc_i++)
	{
		OffsetNumber fc_fromoff = *fc_offnum++;
		OffsetNumber fc_tooff = *fc_offnum++;
		ItemId		fc_fromlp = PageGetItemId(fc_page, fc_fromoff);
		ItemId		fc_tolp PG_USED_FOR_ASSERTS_ONLY;

#ifdef USE_ASSERT_CHECKING

		/*
		 * 我们将设置为LP_REDIRECT的任何现有项（任何'from'项）必须是HOT链中的第一个项。如果该项具有元组存储，则它不能是仅堆栈元组。否则，我们只是维护一个来自已经至少被修剪过一次的现有HOT链的现有LP_REDIRECT。
		 */
		if (!ItemIdIsRedirected(fc_fromlp))
		{
			Assert(ItemIdHasStorage(fc_fromlp) && ItemIdIsNormal(fc_fromlp));

			fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_fromlp);
			Assert(!HeapTupleHeaderIsHeapOnly(fc_htup));
		}
		else
		{
			/* 我们不应该需要冗余地设置重定向 */
			Assert(ItemIdGetRedirect(fc_fromlp) != fc_tooff);
		}

		/*
		 * 我们即将设置为LP_REDIRECT的项（'from'项）将指向一个现有项（'to'项），该项已经是一个仅堆栈元组。每个HOT链最多可以有一个LP_REDIRECT项。
		 *
		 * 我们需要保留一个LP_REDIRECT项（在原始非仅堆栈的根元组被修剪后），以便在整个HOT链变为死亡时，使VACUUM可以轻松确定要从索引中删除的TID。仅堆栈元组永远不能变为LP_DEAD；LP_REDIRECT项或常规堆栈元组可以。
		 *
		 * 此检查可能会遗漏问题，例如重定向的目标可能随后被标记为未使用。下面的page_verify_redirects()检查将捕获此类问题。
		 */
		fc_tolp = PageGetItemId(fc_page, fc_tooff);
		Assert(ItemIdHasStorage(fc_tolp) && ItemIdIsNormal(fc_tolp));
		fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_tolp);
		Assert(HeapTupleHeaderIsHeapOnly(fc_htup));
#endif

		ItemIdSetRedirect(fc_fromlp, fc_tooff);
	}

	/* 更新所有现在已死亡的行指针 */
	fc_offnum = fc_nowdead;
	for (int fc_i = 0; fc_i < fc_ndead; fc_i++)
	{
		OffsetNumber fc_off = *fc_offnum++;
		ItemId		fc_lp = PageGetItemId(fc_page, fc_off);

#ifdef USE_ASSERT_CHECKING

		/*
		 * LP_DEAD行指针必须保留，因为原始项目（对所有人来说都是死的）仍然可以通过索引中的TID被引用。不过，对于任何单独的仅堆元组项目，这通常是不必要的。（尚不清楚这会有多大问题，但没有理由允许它。）
		 */
		if (ItemIdHasStorage(fc_lp))
		{
			Assert(ItemIdIsNormal(fc_lp));
			fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_lp);
			Assert(!HeapTupleHeaderIsHeapOnly(fc_htup));
		}
		else
		{
			/* 整个HOT链变为死状态 */
			Assert(ItemIdIsRedirected(fc_lp));
		}
#endif

		ItemIdSetDead(fc_lp);
	}

	/* 更新所有当前未使用的行指针 */
	fc_offnum = fc_nowunused;
	for (int fc_i = 0; fc_i < fc_nunused; fc_i++)
	{
		OffsetNumber fc_off = *fc_offnum++;
		ItemId		fc_lp = PageGetItemId(fc_page, fc_off);

#ifdef USE_ASSERT_CHECKING

		/*
		 * 只有仅堆元组在修剪过程中可以变为LP_UNUSED。它们
		 * 不需要保留为LP_DEAD项目，直到VACUUM进行索引清理。
		 */
		Assert(ItemIdHasStorage(fc_lp) && ItemIdIsNormal(fc_lp));
		fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_lp);
		Assert(HeapTupleHeaderIsHeapOnly(fc_htup));
#endif

		ItemIdSetUnused(fc_lp);
	}

	/*
	 * 最后，修复任何碎片，并更新页面的提示位以表示
	 * 是否有空闲指针。
	 */
	PageRepairFragmentation(fc_page);

	/*
	 * 现在页面已被修改，断言重定向项目仍指向有效目标。
	 */
	fc_page_verify_redirects(fc_page);
}


/*
 * 如果是通过断言构建的，请验证所有LP_REDIRECT项目都指向有效项目。
 *
 * 与HOT修剪相关的错误表现之一是重定向项目指向
 * 被删除的元组。可靠地检查标记项目
 * 为未使用不会使重定向项目孤立，在heap_prune_chain() /
 * heap_page_prune_execute()期间并不简单，因此我们还会在
 * 修剪后检查整个页面。如果没有此检查，此类错误通常只会导致后续的断言，
 * 可能在损坏引入很久之后。
 *
 * 还检查heap_page_prune_execute()的重定向循环中的注释。
 */
static void fc_page_verify_redirects(Page fc_page)
{
#ifdef USE_ASSERT_CHECKING
	OffsetNumber fc_offnum;
	OffsetNumber fc_maxoff;

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_offnum = FirstOffsetNumber;
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		OffsetNumber fc_targoff;
		ItemId		fc_targitem;
		HeapTupleHeader fc_htup;

		if (!ItemIdIsRedirected(fc_itemid))
			continue;

		fc_targoff = ItemIdGetRedirect(fc_itemid);
		fc_targitem = PageGetItemId(fc_page, fc_targoff);

		Assert(ItemIdIsUsed(fc_targitem));
		Assert(ItemIdIsNormal(fc_targitem));
		Assert(ItemIdHasStorage(fc_targitem));
		fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_targitem);
		Assert(HeapTupleHeaderIsHeapOnly(fc_htup));
	}
#endif
}


/*
 * 在此页面中的所有项目中，找到它们各自的根行指针。
 * 如果项目k是根为项目j的HOT链的一部分，则我们设置
 * root_offsets[k - 1] = j。
 *
 * 传入的root_offsets数组必须有MaxHeapTuplesPerPage个条目。
 * 未使用的条目填充为InvalidOffsetNumber（零）。
 *
 * 此函数必须在缓冲区上至少持有共享锁，以
 * 防止并发修剪操作。
 *
 * 注意：所收集的信息仅在调用者
 * 持有缓冲区的锁定时有效。一旦释放锁定，元组可能会被修剪
 * 并被完全不相关的元组重新使用。
 */
void heap_get_root_tuples(Page fc_page, OffsetNumber *fc_root_offsets)
{
	OffsetNumber fc_offnum,
				fc_maxoff;

	MemSet(fc_root_offsets, InvalidOffsetNumber,
		   MaxHeapTuplesPerPage * sizeof(OffsetNumber));

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_offnum = FirstOffsetNumber; fc_offnum <= fc_maxoff; fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_lp = PageGetItemId(fc_page, fc_offnum);
		HeapTupleHeader fc_htup;
		OffsetNumber fc_nextoffnum;
		TransactionId fc_priorXmax;

		/* 跳过未使用和死掉的项目 */
		if (!ItemIdIsUsed(fc_lp) || ItemIdIsDead(fc_lp))
			continue;

		if (ItemIdIsNormal(fc_lp))
		{
			fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_lp);

			/*
			 * 检查此元组是否是根植于其他元组的HOT链的一部分。
			 * 如果是，现在跳过它；我们将在找到
			 * 它的根时处理它。
			 */
			if (HeapTupleHeaderIsHeapOnly(fc_htup))
				continue;

			/*
			 * 这要么是一个普通的元组，要么是HOT链的根。
			 * 在映射中记住它。
			 */
			fc_root_offsets[fc_offnum - 1] = fc_offnum;

			/* 如果它不是HOT链的开始，我们就完成它了 */
			if (!HeapTupleHeaderIsHotUpdated(fc_htup))
				continue;

			/* 设置以扫描HOT链 */
			fc_nextoffnum = ItemPointerGetOffsetNumber(&fc_htup->t_ctid);
			fc_priorXmax = HeapTupleHeaderGetUpdateXid(fc_htup);
		}
		else
		{
			/* 必须是一个重定向项目。我们不设置它的root_offsets条目 */
			Assert(ItemIdIsRedirected(fc_lp));
			/* 设置以扫描HOT链 */
			fc_nextoffnum = ItemIdGetRedirect(fc_lp);
			fc_priorXmax = InvalidTransactionId;
		}

		/*
		 * 现在沿着HOT链追踪并收集链中的其他元组。
		 *
		 * 注意：尽管这是一个嵌套循环，但该函数的复杂性是O(N)，
		 * 因为页面中的元组不应被访问超过两次，
		 * 一次在外部循环中，一次在HOT链追踪中。
		 */
		for (;;)
		{
			/* 正常性检查（纯粹的偏执） */
			if (fc_offnum < FirstOffsetNumber)
				break;

			/*
			 * 当数组被截断时，可能会出现超出页面行指针数组末尾的偏移量。
			 */
			if (fc_offnum > fc_maxoff)
				break;

			fc_lp = PageGetItemId(fc_page, fc_nextoffnum);

			/* 检查破损的链条 */
			if (!ItemIdIsNormal(fc_lp))
				break;

			fc_htup = (HeapTupleHeader) PageGetItem(fc_page, fc_lp);

			if (TransactionIdIsValid(fc_priorXmax) &&
				!TransactionIdEquals(fc_priorXmax, HeapTupleHeaderGetXmin(fc_htup)))
				break;

			/* 记住该项的根行指针 */
			fc_root_offsets[fc_nextoffnum - 1] = fc_offnum;

			/* 进行到下一个链条成员，如果有的话 */
			if (!HeapTupleHeaderIsHotUpdated(fc_htup))
				break;

			/* HOT意味着它不能移动到不同的分区 */
			Assert(!HeapTupleHeaderIndicatesMovedPartitions(fc_htup));

			fc_nextoffnum = ItemPointerGetOffsetNumber(&fc_htup->t_ctid);
			fc_priorXmax = HeapTupleHeaderGetUpdateXid(fc_htup);
		}
	}
}
